package formal.tree.bst;

import java.util.*;

/**
 * @author DengYuan2
 * @create 2021-01-26 20:55
 */
public class E_501 {
    public static void main(String[] args) {
        Integer[] a = {1, null, 2, 2, null};
        TreeNode treeNode = TreeNode.generateTree(a);
        int[] res = findMode(treeNode);
        System.out.println(Arrays.toString(res));
    }

    /**
     * 我的写法-利用了map来存储每个节点出现的次数
     * 很慢
     */
    public static int max = 0;

    public static int[] findMode(TreeNode root) {
        HashMap<Integer, Integer> map = new HashMap<>(16);
        preOrder(root, map);
        List<Integer> list = new ArrayList<>();
        Set<Integer> set = map.keySet();
        Iterator<Integer> iterator = set.iterator();
        while (iterator.hasNext()) {
            Integer next = iterator.next();
            if (map.get(next) == max) {
                list.add(next);
            }
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    public static void preOrder(TreeNode root, HashMap<Integer, Integer> map) {
        if (root == null) {
            return;
        }
        map.put(root.val, map.getOrDefault(root.val, 0) + 1);
        max = Math.max(max, map.get(root.val));
        preOrder(root.left, map);
        preOrder(root.right, map);
    }

    /**
     * 大神-利用了中序遍历啊！！！
     *
     * @param root
     * @return
     */
    public static int curCount = 1;
    public static int maxCount = 1;
    public static TreeNode pre = null;

    public static int[] findMode2(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        inOrder(root, list);
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    public static void inOrder(TreeNode root, ArrayList<Integer> list) {
        if (root == null) {
            return;
        }
        inOrder(root.left, list);
        if (pre != null) {
            if (pre.val == root.val) {
                curCount++;
            } else {
                curCount = 1;
            }
        }
        if (curCount > maxCount) {
            list.clear();
            list.add(root.val);
            maxCount = curCount;
        } else if (curCount == maxCount) {
            list.add(root.val);
        }
        pre = root;
        inOrder(root.right, list);

    }

    public static int maxNodeCount = 1;
    public static int preValue = -1;
    public static int curNodeCount = 1;


    public static void inOrder2(TreeNode root, ArrayList<Integer> list) {
        if (root == null) {
            return;
        }
        inOrder2(root.left, list);
        if (root.val==preValue){
            curNodeCount++;
        }else {
            preValue=root.val;
            curNodeCount=1;
        }
        if (curNodeCount>maxNodeCount){
            list.clear();
            list.add(root.val);
            maxNodeCount=curNodeCount;
        }else if (curNodeCount==maxNodeCount){
            list.add(root.val);
        }
        inOrder2(root.right,list);
    }

}
